/**
 * \* Created with IntelliJ IDEA.
 * \* User: Administrator
 * \* Date: 2021/11/8
 * \* Time: 10:42
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */



class Node{//节点
    public int data;
    public Node next;//next的类型是ListNode，因为这里的地址存的是节点的地址，所以这里的类型就是节点类型

    public Node(int data){//提供构造方法
        this.data=data;
    }

}
public class MyArrayList {
    public Node head;//链表的头引用

    public void creatList() {
    }
        //头插法
    public void addFirst(int data){
        Node node=new Node(data);

        if(this.head==null){
            //第一次插入节点
            this.head=node;
            return;
        }
        node.next=this.head;
        head=node;

        }
     //尾插法
    public void addLast(int data) {
        Node node=new Node(data);
        Node cur=this.head;

        if (this.head==null){//第一次插入
            this.head=node;
            return;//不return的话，代码继续往下执行
        }
        while (cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;

    }
     //任意位置插入,第一个数据节点为0号下标
     public void addIndex(int index,int data){
        Node node=new Node(data);
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==this.size()){
            addLast(data);
            return;
        }
        //先找到index位置的前一个节点的地址
         Node cur=searchIndex(index);
         //进行插入
         node.next=cur.next;
         cur.next=node;
     }

         private Node searchIndex(int index){

             //1.对index进行合法性检查
             if(index<0||index>this.size()){
                 throw new RuntimeException("index位置不合法");
             }
             Node cur=this.head;
             while (index-1!=0){
                 cur=cur.next;
                 index--;
             }
             return cur;
         }


 //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key) {
         Node cur=this.head;
         while (cur!=null){
             if (cur.data==key){
                 return true;
             }
             cur=cur.next;

         }
         return false;
     }
     //删除第一次出现关键字为key的节点
     public void remove(int key) {
        if (this.head==null){
            System.out.println("单链表为空，不能删除！");
            return;
        }
        if(this.head.data==key){
            this.head=this.head.next;
            return;
        }
        Node cur=searchIndex(key);
        if (cur==null){
            System.out.println("没有你要删除的节点");
            return;
        }
        Node del=cur.next;
        cur.next=del.next;
     }
     //删除所有值为key的节点
     public Node removeAllKey(int key) {
        if (this.head==null)return null;
        Node prev=this.head;
        Node cur=this.head.next;
        while (cur!=null){
            if(cur.data==key){
                prev.next=cur.next;
            }else {
                prev=cur;
                cur=cur.next;
            }
        }
        if(this.head.data==key){
            this.head=this.head.next;
        }
         return this.head;
     }
     //得到单链表的长度
     public int size() {
        int count=0;
        Node cur=this.head;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
     }
     public void display() {
        Node cur=this.head;//定义cur=头
         while (cur!=null){
             System.out.print(cur.data+" ");
             cur=cur.next;

         }
     }
     public void clear(){
        while ((this.head!=null)){
            Node curNext=head.next;
            this.head.next=null;
            this.head=curNext;
        }
    }
}
